# 花式遍历数组的一些问题：
from typing import List
from base import list_2_ListNode, tranverse_listnode


# warm-up:
# 1.1. （151）原地反转字符串： 比如“my name is A.” 反转成"A is name my."
# 需要原地反转：python中的str数据类型不支持，所以无法原地修改
# 技巧是先整个反转，再对每个word反转：
# 最直接的想法是用使用栈
class Reverse_String(object):
    def solution0(self,s):
        # 移除多余空格并分割单词: why？题目要求的不应该有额外的空格
        words = s.strip().split() # split默认单空格或多空格了
        # 反转单词顺序并拼接
        return ' '.join(reversed(words)) # ' '.join(word[::-1])

    # 当然面试官很可能不让你使用集成好的现成的函数
    def solution(self,s):
        # 双指针法：记录每个单词的首尾
        # 倒着找词(因为单词的顺序需要反转)然后再重新拼接到一起：
        s=s.strip()
        i,j=len(s)-1,len(s)-1
        words=[]
        while i>=0:
            # 找空格
            while i>=0 and s[i] !=' ': i-=1 #i找到单词的词尾，j在原处存的是单词的开头; 不加>=0条件的话就会倒着又来一遍了
            words.append(s[i+1:j+1]) # i+1是因为i遇到了空格才跳出while，j+1是因为切片的最后一位索引是不会被取到的
            while i>=0 and s[i]==' ': i-=1 # i找到了（多个）空格，同样需要移动
            j=i
        return ' '.join(words)

    def test(self):
        s='there   is still time left'
        res=self.solution(s)
        print(res)

# warm up 2: 61 旋转链表：给你一个单链表，让你旋转链表，将链表每个节点向右移动 k 个位置。
# 比如说输入单链表 1 -> 2 -> 3 -> 4 -> 5，k = 2，你的算法需要返回 4 -> 5 -> 1 -> 2 -> 3，即将链表每个节点向右移动 2 个位置。
# 思路：先反转整个链表：5 -> 4 -> 3 -> 2 -> 1，再分别反转前k个节点和后n-k个节点：4 -> 5 -> 1 -> 2 -> 3
# 算法的最底层是对数据结构的深刻理解
class Reverse_Listnode(object):
    def solution(self,head,k):
        # 先反转整个链表：
        pre=None
        cur=head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        # 此时head: 5 -> 4 -> 3 -> 2 -> 1
        # 然后对前k个节点进行反转：
        cur=pre
        pre=None
        i=0
        while cur and i<k:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
            i+=1
        head1=pre # 4 -> 5
        # 此时的链表是这样： 4 -> 5 -> None, 3 -> 2 -> 1
        pre=None
        cur=temp
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        head2=pre # 这里是 1 -> 2 -> 3
        # 拼接：
        res=head1
        cur=head1
        while cur and cur.next:
            cur=cur.next
        cur.next=head2
        return head1

    def test(self):
        head=list_2_ListNode([1,2,3,4,5])
        res= self.solution(head,2)
        tranverse_listnode(res)

## 矩阵：
# 1. 48. 旋转图像 | 力扣 | LeetCode |  🟠
# 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
# 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
# 思路是先将矩阵按照左斜对角线镜像，然后每行反转数组 ！！⭐记住这个技巧
class Pivot_Matrix(object):
    def solution(self,matrix: List)-> List:
        # matrix是二维数组：
        n=len(matrix)
        for i in range(n):
            for j in range(i,n):
                temp=matrix[i][j]
                matrix[i][j]=matrix[j][i]
                matrix[j][i]=temp
        # 翻转每行：
        for i in range(n):
            for j in range(n//2):
                temp=matrix[i][j]
                matrix[i][j]=matrix[i][n-1-j]
                matrix[i][n-1-j]=temp
        return matrix

    def test(self):
        matrix=[[1,2,3],[4,5,6],[7,8,9]]
        res=self.solution(matrix)
        print(res)

# 2. 54. 螺旋矩阵 | 力扣 | LeetCode |  🟠
# 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
# 解题的核心思路是按照右、下、左、上的顺序遍历数组，并使用四个变量圈定未遍历元素的边界：
# 难点在边界条件极其变化 ！！ ⭐ 记住，这个临时想不出来
class Spiral_Matrix(object):
    def solution(self,matrix)->List:
        m=len(matrix)
        n=len(matrix[0])
        upper_bound,lower_bound=0,m-1
        left_bound,right_bound=0,n-1
        res=[]
        while len(res)<=m*n:
            if upper_bound<=lower_bound: # 满足时说明有左到右的数还可以循环
                for j in range(left_bound,right_bound+1):
                    res.append(matrix[upper_bound][j])
                upper_bound=+1
            if left_bound<=right_bound:
                for i in range(upper_bound,lower_bound+1):
                    res.append(matrix[i][right_bound])
                right_bound-=1
            if upper_bound<=lower_bound:
                for j in range(right_bound,left_bound-1,-1):
                    res.append(matrix[lower_bound][j])
                lower_bound-=1
            if left_bound<=right_bound:
                for i in range(lower_bound,upper_bound-1,-1):
                    res.append(matrix[i][left_bound])
                left_bound+=1
        return res

    def test(self):
        matrix=[[1,2,3,4],[5,6,7,8],[9,10,11,12]]
        res=self.solution(matrix)
        print(res)
# 3. 自己构造螺旋矩阵：给你一个整数n，构造1 ~ n^2的正方形螺旋矩阵：
class Make_Spiral_Matrix(object):
    def solution(self,n):
        upper_bound,lower_bound=0,n-1
        left_bound,right_bound=0,n-1
        matrix=[[0]*n for _ in range(n)] # 这里不能写成[[0]*n]*n，赋值的时候会有大问题！！ ⭐
        k=1
        while k <=n*n:
            if upper_bound<=lower_bound:
                for j in range(left_bound,right_bound+1):
                    matrix[upper_bound][j]=k
                    k+=1
                upper_bound+=1
            if left_bound<=right_bound:
                for i in range(upper_bound,lower_bound+1):
                    matrix[i][right_bound]=k
                    k+=1
                right_bound-=1
            if upper_bound<=lower_bound:
                for j in range(right_bound,left_bound-1,-1):
                    matrix[lower_bound][j]=k
                    k+=1
                lower_bound-=1
            if left_bound<=right_bound:
                for i in range(lower_bound,upper_bound-1,-1):
                    matrix[i][left_bound]=k
                    k+=1
                left_bound+=1
        return matrix

    def test(self):
        n=4
        res=self.solution(n)
        print(res)

if __name__ == '__main__':
    Make_Spiral_Matrix().test()